public class Main {
    public int numDistinct(String s, String t) {
        int m = s.length(),n = t.length();
        int[][] dp = new int[m+1][n+1]; //区间内s子序列包含t的个数
        for(int i = 0;i <= m;i++) dp[i][0] = 1;
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if(s.charAt(i-1) == t.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                dp[i][j] += dp[i-1][j];
            }
        }
        return dp[m][n];
    }
////////////////////////////////////////////////////////
    public String multiply(String num1, String num2) {
        int m = num1.length(),n = num2.length();
        int[] tmp = new int[m+n-1];
        //先无进位相乘，然后相加，再处理进位
        StringBuilder s1 = new StringBuilder(num1);
        StringBuilder s2 = new StringBuilder(num2);
        s1.reverse();  s2.reverse();
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                tmp[i+j] += ((s1.charAt(i)-'0')*(s2.charAt(j)-'0'));
            }
        }
        StringBuilder ret = new StringBuilder();
        int carry = 0;
        for(int i = 0;i < m+n-1;i++) {
            int sum = (tmp[i] + carry) % 10;
            ret.append(sum);
            carry = (tmp[i] + carry) / 10;
        }
        if(carry != 0) ret.append(carry);
        ret.reverse();
        return ret.toString();
    }


    public static void main(String[] args) {
        Main main = new Main();
        main.multiply("123","456");

    }
}
